This invention relates to image data compression based on border following and by the encoding of the inner and outer boundaries of objects.
It is well appreciated in the art that a huge two dimensional array of Boolean coded points representative of a black/white image for even a single 81/2 .times. 11 inches page is so large as to require compression in most applications. Techniques for achieving this redundancy reduction typically utilize a two-stage process. First, the image is passed through a predictor or prewhitener which, for example, may predict the black/white state of each picture element on the basis of information about the previous pel (picture element) and scan line. The predictor transmits 0' or 1' to the encoder depending upon whether the predicted value is correct or in error. In the second step, the resulting "error image" is compressed by run length encoding. Illustrative of such prediction/run length encoding may be found for example, in R. B. Arps, "Systems for Compression of Digital Data," U.S. Pat. No. 3,813,485 issued on My 28, 1974.
In general, predictive/run length encoding has two disadvantages. First, it is one dimensional in that each scan line is operated on separetely with the possible exception of the previous scan line information. Secondly, image manipulation operations cannot be conveniently performed on the compressed image data. This arises, in part, from the fact that the process of predicting and run length encoding obscures some relational data among the points in the compressed image that were to be found in the original image. Also, encoding is done by scan line, as opposed to encoding by object. This relational data can be recovered upon expansion of the compressed data. However, its absence when the data is in a compressed form means that any operation performed upon the compressed data is very tedious and, in fact, is equivalent to expanding the image first. The encoding of object boundaries as another method for achieving image compression suffers neither the disadvantage of one dimensionality nor the loss of relational data.
In the specification, an image is considered to be a two-dimensional array of points, each of which exhibits a Boolean value representative of a black or white picture element. A cluster of black elements is defined as a connected object if it possesses a single outer boundary closing upon itself.
The notion of boundary encoding, as suggested above, of the outer contours of a black object on a white background is not new. Methods for achieving this result may be found in Rosenfield, "Picture Processing by Computer", Academic Press, New York, Library of Congress No. 78-84255, at pp. 134-138. Also, one may find methods/algorithms in the literature which locate and organize lists of objects boundary contours. However, most of the methods/algorithms appear to operate on grey scale information. The few black/white algorithms appearing in the literature are at least partially raster based, thus requiring many passes over the entire array. Also, they require frequent reference to temporary lists or tags which constitute intermediate image planes for image processing purposes. Typically, the prior art methods/algorithms require several bits of storage for each picture element being processed. This requirement exists in order to identify those elements which are already in a chain and to distinguish boundary elements from interior elements.